분할 정복(Divide and Conquer)
DP(Dynamic Programming)와 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
DP와 분할정복의 차이점은 부분 문제의 중복
DP 문제에서는 각 부분 문제들이 서로 영향을 미치며, 부분 문제가 중복된다
반면에 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다
분할 정복 기법
- 분할 : 해결할 문제를 여러 개의 작은 부분으로 나눈다
- 정복 : 나눈 작은 문제를 각각 해결한다
- 통합 : 필요하다면 해결된 해답을 모은다
예시
퀵 정렬(Quick Sort)
거듭제곱
이진검색
병합 정렬